# -*-* encoding:UTF-8 -*-
# author            : mengy
# date              : 2018/12/26
# python-version    : Python 3.7.0
# description       : 证明哥德巴赫猜想
#   哥德巴赫猜想:任何一个大于2的偶数都能表示为两个素数之和。

import time
import math


def is_prime(m):
    """
    判断一个数是否为素数(质数) \n
    时间复杂度:O(n^1/2)
    :param m:
    :return:
    """
    if m <= 1:
        return False
    elif m == 2:
        return True
    else:
        for i in range(2, int(math.sqrt(m)) + 1, 1):
            if m % i == 0:
                return False
    return True


def binary_search(list, n):
    """
    二分查找 \n
    时间复杂度:O(log2n),（是以2为底，n的对数）
    :param list:
    :param n:
    :return:
    """
    start = 0
    end = len(list) - 1
    while start <= end:
        mid = int((start + end) / 2)
        if n > list[mid]:
            start = mid + 1
        elif n < list[mid]:
            end = mid - 1
        else:
            return mid
    return -1


def verify_origin(n):
    """
    输出给定范围内的偶数是否满足哥德巴赫猜想（原始算法） \n
    时间复杂度:O(n^5/2)
        算法待优化点:
            1、偶数分解存在重复，例如:i = 4 分解为（2，2）（3，1），i = 6 分解为（2，4）（3，3）（4，2）（5，1）...
               除最后一项，每一项都在 i / 2 处对称
            2、素数判断存在重复，例如:i = 4 分解为（2，2）（3，1），要判断第一个2是是否为素数，然后判断第二个2是否为素数
    :param n:
    :return:
    """
    times = 0;
    if n <= 2 or n % 2 != 0:
        print("请给出一个大于2的偶数")
    else:
        # 从4开始递增，每次增加2，直到给定的偶数为止（包含给定的偶数）
        for i in range(4, n + 2, 2):
            # 分解每一个偶数，找到所有能分解的素数
            for j in range(2, i):
                if is_prime(j) and is_prime(i - j):
                    times += 1
                    # print("%d. %d 可表示为 %d 和 %d 两个素数之和" % (times, i, j, i - j))
                    break


def verify_improve1(n):
    """
    输出给定范围内的偶数是否满足哥德巴赫猜想（算法改进方案一） \n
    时间复杂度为:O(n^2)
    :param n:
    :return:
    """
    times = 0;
    if n <= 2 or n % 2 != 0:
        print("请给出一个大于2的偶数")
    map = [False]
    # 先遍历给定范围内所有数，判断是否为素数，并生成一个list
    for key in range(n + 1):
        map.append(is_prime(key))
    for i in range(4, n + 2, 2):
        for j in range(2, i):
            if map[j] and map[i - j]:
                times += 1
                # print("%d. %d 可表示为 %d 和 %d 两个素数之和" % (times, i, j, i - j))
                break


def verify_improve2(n):
    """
    输出给定范围内的偶数是否满足哥德巴赫猜想（算法改进方案二） \n
    时间复杂度:O(n^2logn)
    :param n:
    :return:
    """
    times = 0;
    if n <= 2 or n % 2 != 0:
        print("请给出一个大于2的偶数")
    map = []
    # 先遍历给定范围内所有数，筛选所有素数
    for prime in range(3, n + 2, 2):
        if is_prime(prime):
            map.append(prime)
    for i in range(4, n + 2, 2):
        for j in range(2, i):
            if -1 != binary_search(map, j) and -1 != binary_search(map, i - j):
                times += 1
                # print("%d. %d 可表示为 %d 和 %d 两个素数之和" % (times, i, j, i - j))
                break


def verify_improve3(n):
    """
    输出给定范围内的偶数是否满足哥德巴赫猜想（算法改进方案三） \n
    时间复杂度为:O(n^2)
    :param n:
    :return:
    """
    times = 0;
    if n <= 2 or n % 2 != 0:
        print("请给出一个大于2的偶数")
    map = []
    # 先遍历给定范围内所有数，筛选所有素数
    for prime in range(3, n + 2, 2):
        if is_prime(prime):
            map.append(prime)
    for i in range(len(map)):
        for j in range(len(map)):
            if map[i] + map[j] == n:
                times += 1
                # print("%d. %d 可表示为 %d 和 %d 两个素数之和" % (times, i, j, i - j))
                break


if __name__ == '__main__':
    start = time.time() * 1000000
    verify_origin(2000)
    print("总共耗时 %d us" % (time.time() * 1000000 - start))
    print("--" * 15)
    start2 = time.time() * 1000000
    verify_improve1(2000)
    print("总共耗时 %d us" % (time.time() * 1000000 - start2))
    print("--" * 15)
    start3 = time.time() * 1000000
    verify_improve2(2000)
    print("总共耗时 %d us" % (time.time() * 1000000 - start3))
    print("--" * 15)
    start4 = time.time() * 1000000
    verify_improve3(2000)
    print("总共耗时 %d us" % (time.time() * 1000000 - start4))

    # list = [1, 2, 5, 6, 7, 8, 9, 10, 15, 16, 40, 49, 59, 78, 89]
    # print(binary_search(list, 1))
